package com.onepiece.shipelves.common.myutils.tree;

import com.onepiece.shipelves.common.myutils.tree.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;


public class CommonAncestor {

    //在二叉搜索树中查找最大公共祖先，1.直接递归如果p和q都小于root就往左，如果一个大一个小说明就是公共祖先，如果root是空说明没有找到
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (p == null || q == null || root == null) {
            return null;
        }
        if (p.val < root.val && q.val < root.val) {
            return lowestCommonAncestor(root.left, p, q);
        }
        if (p.val > root.val && q.val > root.val) {
            return lowestCommonAncestor(root.right, p, q);
        }
        return root;
    }

    //在二叉搜索树中查找最大公共祖先，1.采用迭代如果p和q都小于root就往左，如果一个大一个小说明就是公共祖先，如果root是空说明没有找到
    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode ancestor = root;
        while (true) {
            if (p.val < ancestor.val && q.val < ancestor.val) {
                ancestor = ancestor.left;
            } else if (p.val > ancestor.val && q.val > ancestor.val) {
                ancestor = ancestor.right;
            } else {
                break;
            }
        }
        return ancestor;
    }


    //在二叉搜索树中查找最大公共祖先，保存到节点的路径，然后从上到下，如果路径出现不一致，就break，输出父节点
    public TreeNode lowestCommonAncestor3(TreeNode root, TreeNode p, TreeNode q) {
        List<TreeNode> path_p = getPath(root, p);
        List<TreeNode> path_q = getPath(root, q);
        TreeNode ancestor = null;
        for (int i = 0; i < path_p.size() && i < path_q.size(); ++i) {
            if (path_p.get(i) == path_q.get(i)) {
                ancestor = path_p.get(i);
            } else {
                break;
            }
        }
        return ancestor;
    }

    public List<TreeNode> getPath(TreeNode root, TreeNode target) {
        List<TreeNode> path = new ArrayList<TreeNode>();
        TreeNode node = root;
        while (node != target) {
            path.add(node);
            if (target.val < node.val) {
                node = node.left;
            } else {
                node = node.right;
            }
        }
        path.add(node);
        return path;
    }

    private List<List<Integer>> ret;

    //因为要分层输出，所以考虑要能把这个层抽出来，然后考虑到遍历的几种方式，都是递归迭代的并非能够获得某一层的节点
    //所以考虑要使用一个数组来存储，在遍历的过程中根据层数把节点的值放入相应层数的数据结构中。
    public List<List<Integer>> levelOrder(TreeNode root) {
        ret = new ArrayList<>();
        dfs(0, root);
        return ret;
    }

    //
    private void dfs(int depth, TreeNode root) {
        if (root == null) {
            return;
        }
        if (ret.size() == depth) {
            ret.add(new ArrayList<>());
        }
        ret.get(depth).add(root.val);
        dfs(depth + 1, root.left);
        dfs(depth + 1, root.right);
    }

    //因为要分层输出，所以考虑要能把这个层抽出来，然后考虑到遍历的几种方式，都是递归迭代的并非能够获得某一层的节点
    //所以不是原来的遍历思路，所以要逐层把节点放到队列中，然后循环取出
    public List<List<Integer>> levelOrder2(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<>();
        if (root == null) {
            return ret;
        }
        List<Integer> tmp = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                root = queue.poll();
                tmp.add(root.val);
                if (root.left != null) {
                    queue.add(root.left);
                }
                if (root.right != null) {
                    queue.add(root.right);
                }
            }
            ret.add(new ArrayList<>(tmp));
            tmp.clear();
        }
        return ret;
    }
    //寻找二叉树公共父节点，方法一可以
    public TreeNode lowestCommonAncestor4(TreeNode root, TreeNode p, TreeNode q){
        if(root == null || root == q || root == p)return root;
        TreeNode left = lowestCommonAncestor4(root.left, p, q);
        TreeNode right = lowestCommonAncestor4(root.right, p, q);
        if(left == null && right == null)return null;
        if(left == null)return right;
        if(right == null)return left;
        return root;
    }

}
